package a2025_03_15;

import java.util.LinkedList;
import java.util.Queue;

public class demo1 {
    public static int[] dr=new int[]{1,-1,0,0};
    public static int[] dc=new int[]{0,0,1,-1};
    public static boolean[][] visit;
    public static void main(String[] args) {
        char[][] board=new char[][]{{'X','O','X'},{'X','O','X'},{'X','O','X'}};
        int m=board.length;
        int n=board[0].length;
        visit=new boolean[m][n];
        for(int i=0;i<m;i++){
            if(i==0||i==m-1){
                for(int j=0;j<n;j++){
                    if(board[i][j]=='O'&&!visit[i][j]){
                        bfs(i,j,'O','?',board);
                    }
                }
            }else{
                for(int j=0;j<n;j+=(n-1)){
                    if(board[i][j]=='O'&&!visit[i][j]){
                        bfs(i,j,'O','?',board);
                    }
                }
            }
        }
        visit=new boolean[m][n];
        for(int i=1;i<m-1;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='O'&&!visit[i][j]){
                    bfs(i,j,'O','X',board);
                }
            }
        }
        visit=new boolean[m][n];
        for(int i=0;i<m;i++){
            if(i==0||i==m-1){
                for(int j=0;j<n;j++){
                    if(board[i][j]=='?'&&!visit[i][j]){
                        bfs(i,j,'?','O',board);
                    }
                }
            }else{
                for(int j=0;j<n;j+=(n-1)){
                    if(board[i][j]=='?'&&!visit[i][j]){
                        bfs(i,j,'?','O',board);
                    }
                }
            }
        }
        System.out.println();
    }
    public static void bfs(int i,int j,char target,char desc,char[][] board){
        Queue<int[]> queue=new LinkedList<>();
        board[i][j]=desc;
        visit[i][j]=true;
        queue.add(new int[]{i,j});

        int m=board.length;
        int n=board[0].length;

        while(!queue.isEmpty()){
            int[] temp=queue.poll();
            for(int k=0;k<4;k++){
                int r=temp[0]+dr[k];
                int c=temp[1]+dc[k];
                if(r>=0&&r<m&&c>=0&&c<n&&board[r][c]==target&&!visit[r][c]){
                    board[r][c]=desc;
                    visit[r][c]=true;
                    queue.add(new int[]{r,c});
                }
            }
        }
    }
}
